package site.wanjiahao.list;

import java.util.Iterator;

public class ArrayList<E> extends AbstractList<E> implements Iterable<E> {

    private Object[] elements;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        if (capacity <= DEFAULT_CAPACITY) {
            capacity = DEFAULT_CAPACITY;
        }
        elements = new Object[capacity];
    }

    @Override
    public void add(E ele) {
        // 添加元素至线性表头部
        add(size, ele);
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return (E) elements[index];
    }

    @Override
    public E set(int index, E ele) {
        rangeCheck(index);
        E old = (E) elements[index];
        elements[index] = ele;
        return old;
    }

    /*
    *  最好:  O(1) 在动态数组最后面添加
    *  最坏   O(n) 在动态数组起始位置添加
    *  平均复杂度  O(n)
    * */
    @Override
    public void add(int index, E ele) {
        // 判断添加索引是否合法
        rangeCheckForAdd(index);
        // 确保线性表容量足够
        ensureCapacity();
        // 判断是否在队尾添加元素
        if (index == size) {
            elements[size++] = ele;
            return;
        }
        if (size - index >= 0)
            System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = ele;
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        // 直接覆盖法
        E old = (E) elements[index];
        if (size - 1 - index >= 0)
            System.arraycopy(elements, index + 1, elements, index, size - 1 - index);
        // 释放指向内存
        elements[--size] = null;
        // 缩容操作
        trim();
        return old;
    }

    // 当前剩余容量大于总容量一半，进行缩容操作
    private void trim() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1;

        if (size > newCapacity || size <= DEFAULT_CAPACITY) return;

        // 缩容
        Object[] newAry = new Object[newCapacity];
        System.arraycopy(elements, 0, newAry, 0, size);
        elements = newAry;
        System.out.println("进行缩容操作: oldCapacity" + oldCapacity + " newCapacity" + newCapacity);
    }

    @Override
    public int indexOf(E ele) {
        // 使用equals方法比较，比较判断条件扩展性高，而不是直接比较内存地址
        if (ele != null) {
            for (int i = 0; i < size; i++) {
                if (ele.equals(elements[i])) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (null == elements[i]) {
                    return i;
                }
            }
        }
        return NOT_FOUND_ELEMENT;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            // 释放内存数据
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public String toString() {
        int end = size - 1;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elements[i]);
            if (i != end) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new DefaultIter();
    }

    private void ensureCapacity() {
        int capacity = size + 1;
        int oldCapacity = elements.length;
        // 判断容量是否足够
        if (capacity >= oldCapacity) {
            // 增加1.5倍容量
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            Object[] newAry = new Object[newCapacity];
            // 拷贝数组
            if (size >= 0) System.arraycopy(elements, 0, newAry, 0, size);
            elements = newAry;
            System.out.println("进行扩容操作: oldCapacity" + oldCapacity + " newCapacity" + newCapacity);
        }
    }

}
